import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                ", next=" + next +
                ", random=" + random +
                '}';
    }
    //    public Node head;
}
public class NM2 {

//给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，
// 该指针可以指向链表中的任何节点或空节点。
// 构造这个链表深拷贝.深拷贝应该正好由 n个全新节点组成，
// 其中每个新节点的值都设为其对应的原节点的值。
// 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，
// 并使原链表和复制链表中的这些指针能够表示相同的链表状态。
// 复制链表中的指针都不应指向原链表中的节点 。
    public static void randomList(Node head){
        Map<Node,Node> map=new HashMap<>();
        Node cur=head;
        //1.进行第一次遍历这个原来的链表，将其链表中的值进行赋值；
        // 并将每个原节点对应复制出来的新节点保存到map集合中；
        while(cur!=null){
            Node node=new Node(cur.val);
            map.put(cur,node);
            cur=cur.next;
        }
        //2,进行第二次的遍历，链表，即进行深拷贝这个节点；
        //深拷贝：与原节点的值一样，但是其他的阈值不一样，属于重新创建一个新的节点；
         cur=head;
        while(cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        System.out.println(map);
    }
    public static Node  createNode(){

        	    Node node1=new Node(12);
            	    Node node2=new Node(23);
            	    Node node3=new Node(34);
            	    Node node4=new Node(45);
            	    Node node5=new Node(56);
            	    node1.next=node2;
            	    node2.next=node3;
            	    node3.next=node4;
            	    node4.next=node5;
            	     Node head=node1;
                     return head;
            	}

    public static void main(String[] args){
        randomList( createNode());
    }
}
